916. Interesting product

Determine all possible values of the product i * j, where the integer variables i and j vary within the ranges i from a to b and j from c to d (1 ≤ a, b, c, d ≤ 10).

Input. One single line contains four integers a, b, c, and d (a may be greater than b, and c may be greater than d).

Output. Print the number of unique possible values of the product.

Sample input 1	Sample output 1
1 10 1 10	42
Sample input 2	Sample output 2
4 2 5 2	9

SOLUTION

map data structure

Algorithm analysis

Declare a data structure map<int, int> m to count how many times the product i * j occurs. The number of unique products is equal to the size of the map m.

Example

Let’s consider the second example. Let’s write the multiplication table for the matrix [2; 4] * [2; 5].

The table contains 9 unique values.

Algorithm implementation

Declare a structure for storing data.

map<int, int> m;

Read the input data.

scanf("%d %d %d %d",&a,&b,&c,&d);

Swap a and b, as well as c and d, to ensure the conditions a ≤ b, c ≤ d are satisfied.

if (a > b) swap(a,b);

if (c > d) swap(c,d);

Iterate through all possible products i * j. For each product, increment by 1 the value associated with the key i * j in the map.

for(i = a; i <= b; i++)

for(j = c; j <= d; j++)

m[i*j]++;

Print the result – the size of the map m.

printf("%d\n",m.size());

Java implementation

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Read the input data.

int a = con.nextInt();

int b = con.nextInt();

int c = con.nextInt();

int d = con.nextInt();

Swap a and b, as well as c and d, to ensure the conditions a ≤ b, c ≤ d are satisfied.

if (a > b) {int temp = a; a = b; b = temp;}

if (c > d) {int temp = c; c = d; d = temp;}

Declare a structure for storing data.

Map<Integer,Integer> m = new HashMap<Integer,Integer>();

Iterate through all possible products i * j.

for(int i = a; i <= b; i++)

for(int j = c; j <= d; j++)

{

int key = i * j;

Increment by 1 the value associated with the key i * j. If no value is associated with the key yet, default it to 0.

m.put(key, m.getOrDefault(key, 0) + 1);

}

Print the result – the size of the map m.

System.out.println(m.size());

con.close();

}

}

Python implementation

Read the input data.

a, b, c, d = map(int, input().split())

Declare a dictionary for storing data.

m = {}

Swap a and b, as well as c and d, to ensure the conditions a ≤ b, c ≤ d are satisfied.

if a > b:

a, b = b, a

if c > d:

c, d = d, c

Iterate through all possible products i * j. For each product, increment by 1 the value associated with the key i * j in the dictionary.

for i in range(a, b+1):

for j in range(c, d+1):

key = i * j

m[key] = m.get(key, 0) + 1

Print the result – the size of the dictionary m.

print(len(m))